TY - JOUR
T1 - Maximal lifetime scheduling for K to 1 sensor-target surveillance networks
AU - Liu, Hai
AU - Wan, Pengjun
AU - Jia, Xiaohua
PY - 2006/10/18
Y1 - 2006/10/18
N2 - This paper addresses the maximal lifetime scheduling for k to 1 sensor-target surveillance networks. Given a set of sensors and targets in Euclidean plane, a sensor can watch only one target at a time and a target should be watched by k sensors (k ≥ 2) at anytime. Our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. Our solution consists of three steps: (1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; (2) decomposing the workload matrix into a sequence of schedule matrices by extending the Hall's theory, to achieve the maximal lifetime; (3) obtaining a target watching timetable for each sensor based on the schedule matrices. The time complexity of our optimal method is O(m2n3), where m, n are the number of targets and the number of sensors, respectively. We illustrate our optimal method by a numeric example and experiments in the end. © 2005 Elsevier B.V. All rights reserved.
AB - This paper addresses the maximal lifetime scheduling for k to 1 sensor-target surveillance networks. Given a set of sensors and targets in Euclidean plane, a sensor can watch only one target at a time and a target should be watched by k sensors (k ≥ 2) at anytime. Our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. Our solution consists of three steps: (1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; (2) decomposing the workload matrix into a sequence of schedule matrices by extending the Hall's theory, to achieve the maximal lifetime; (3) obtaining a target watching timetable for each sensor based on the schedule matrices. The time complexity of our optimal method is O(m2n3), where m, n are the number of targets and the number of sensors, respectively. We illustrate our optimal method by a numeric example and experiments in the end. © 2005 Elsevier B.V. All rights reserved.
KW - Energy efficiency
KW - Lifetime
KW - Scheduling
KW - Sensor network
KW - Surveillance system
UR - http://www.scopus.com/inward/record.url?scp=33746591732&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33746591732&origin=recordpage
U2 - 10.1016/j.comnet.2005.11.001
DO - 10.1016/j.comnet.2005.11.001
M3 - 21_Publication in refereed journal
VL - 50
SP - 2839
EP - 2854
JO - Computer Networks
JF - Computer Networks
SN - 1389-1286
IS - 15
ER -