Scheduling Resource-Bounded Monitoring Devices for Event Detection and Isolation in Networks

In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, monitoring devices have limited energy supplies, and they can operate for a limited duration. As a result, energy-efficient monitoring of target locations through a set of monitoring devices with limited energy supplies is a crucial problem in networked systems. In this paper, we study optimal scheduling of monitoring devices to maximize network coverage for detecting and isolating events on targets for a given network lifetime. The monitoring devices considered could remain active only for a fraction of the overall network lifetime. We formulate the problem of scheduling of monitoring devices as a graph labeling problem, which unlike other existing solutions, allows us to directly utilize the underlying network structure to explore the trade-off between coverage and network lifetime. In this direction, first we present a greedy heuristic, and then a game-theoretic solution to the graph labeling problem. The proposed setup can be used to simultaneously solve the scheduling and placement of monitoring devices, which, as our simulations illustrate, gives improved performance as compared to separately solving the placement and scheduling problems. Finally, we illustrate our results on various networks, including real-world water distribution networks and random geometric networks.