334 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 2, APRIL 2007Maximizing Lifetime of Sensor Surveillance SystemsHai Liu, Xiaohua Jia, Peng-Jun Wan, Chih-Wei Yi, S. Kami Makki, and Niki PissinouAbstract—This paper addresses the maximal lifetime schedulingproblem in sensor surveillance systems. Given a set of sensors andtargets in an area, a sensor can watch only one target at a time, ourtask is to schedule sensors to watch targets and forward the senseddata to the base station, such that the lifetime of the surveillancesystem is maximized, where the lifetime is the duration that all tar-gets are watched and all active sensors are connected to the basestation. We propose an optimal solution to find the target-watchingschedule for sensors that achieves the maximal lifetime. Our solu-tion consists of three steps: 1) computing the maximal lifetime ofthe surveillance system and a workload matrix by using the linearprogramming technique; 2) decomposing the workload matrix intoa sequence of schedule matrices that can achieve the maximal life-time; and 3) determining the sensor surveillance trees based on theabove obtained schedule matrices, which specify the active sensorsand the routes to pass sensed data to the base station. This is thefirst time in the literature that the problem of maximizing lifetimeof sensor surveillance systems has been formulated and the optimalsolution has been found.Index Terms—Energy efficiency, lifetime, scheduling, sensor net-work, surveillance system.I. INTRODUCTIONSASENSOR SURVEILLANCE system consists of a set ofwireless sensor nodes (sensors for short) and a set of tar-gets to be monitored. The sensors collaborate with each otherto watch or monitor the targets and pass the sensed data to thebase station. The sensors are powered by batteries and have astringent power budget [1], [2]. The nature of the sensor surveil-lance system requires a long lifetime. In this paper, we discuss amaximal lifetime problem in sensor surveillance systems. Givena set of targets, a set of sensors, and a base station (BS) inan area, the sensors are used to watch the targets and collectsensed data to the BS. Each sensor has an initial energy reserve,a fixed surveillance range, and an adjustable transmission range.A sensor can watch at most one target at a time and a targetManuscript received April 28, 2005; revised April 14, 2006; approved byIEEE/ACM TRANSACTIONS ON NETWORKING Editor N. Shroff. This work wassupported in part by Hong Kong Research Grant Council under Grant No. CityU114505, NSF China Grant No. 60633020, and NSF CCR-0311174.H. Liu and X. Jia are with the Department of Computer Science, City Uni-versity of Hong Kong, Kowloon, Hong Kong (e-mail: [email protected];[email protected]).P.-J. Wan is with the Department of Electrical Engineering and Computer Sci-ence, Illinois Institute of Technology, Chicago, IL 60616 USA (e-mail: [email protected]).C.-W. Yi is with the Department of Computer Science, National Chiao TungUniversity, Hsinchu, Taiwan 300, R.O.C. (e-mail: [email protected]).S. K. Makki is with the Department of Electrical Engineering and Com-puter Science, University of Toledo, Toledo, OH 43606-3390 USA (e-mail:[email protected]).N. Pissinou is with the Telecommunications and Information TechnologyInstitute, Florida International University, Miami, FL 33174 USA (e-mail:[email protected]).Digital Object Identifier 10.1109/TNET.2007.892883should be watched by a sensor at any time. The problem is toschedule a subset of sensors to be active at a time to watch thetargets and find the routes for the active sensors to send databack to the BS, such that the lifetime of the entire sensor net-work is maximized. The lifetime is the duration up to the timewhen there exists one target that can no longer be watched byany sensors or data cannot be forwarded to the BS any longerdue to the depletion of energy of the sensor nodes. We assumethe positions of targets, sensors, and the BS are given in priorand static. The location information of both sensors and targetscan be obtained via a distributed monitoring mechanism [3] orthe scanning method [4], [5] by the BS.The solution to this problem includes two parts: schedulingthe sensors to watch targets and routing the sensed data to theBS. The schedule and the routes are pre-computed at the BS,and they are disseminated to sensors by the BS at the systeminitialization. When the system starts operation, all sensors workaccording to the schedule, such as when and for what durationto sleep, watch targets, or relay messages.There are many applications of this type of surveillance sys-tems. For example, sensors equipped with camera are used toguard cargo containers to prevent them from being tamperedduring the long journey of shipment or during the storage at aport. Another example is the use of sensors to monitor somehot spots in a region or in a building. In these examples, sen-sors and targets are static, and each sensor can only focus onwatching one target at a time. For the applications in which onesensor can watch multiple targets simultaneously, some workon sensor scheduling has been done in [2] and [6], where sen-sors are scheduled to work in turn such that a given area can becovered fully [2] or partially [6] and the system lifetime is max-imized.The rest of this paper is organized as follows. Section IIis related work and Section III is the problem definition.Section IV presents our solution which consists of three parts.Section IV-A gives a linear programming formulation thatis used to compute the maximal lifetime of the surveillancesystem. In Section IV-B, we show that the maximal lifetime isachievable, and give the algorithms for scheduling the sensorsto watch targets. Section IV-C discusses surveillance trees forrouting sensed data to BS. Section V gives a numeric examplesolved by using our method and simulation results. We con-clude our work in Section VI.II. RELATED WORKThere are two major techniques for maximizing the sensornetwork lifetime: the use of energy efficient routing and the in-troduction of sleep/active modes for sensors.Extensive research has been done on energy efficient datagathering and information dissemination in sensor networks.Some well-known energy efficient protocols were developed,1063-6692/$25.00 © 2007 IEEELIU et al.: MAXIMIZING LIFETIME OF SENSOR SURVEILLANCE SYSTEMS 335such as Directed Diffusion [7], LEACH [8], PEGASIS [9], andACQUIRE [10]. Directed Diffusion is regarded as