skip to main content
article

Maximizing lifetime of sensor surveillance systems

Published: 01 April 2007 Publication History

Abstract

This paper addresses the maximal lifetime scheduling problem in sensor surveillance systems. Given a set of sensors and targets in an area, a sensor can watch only one target at a time, our task is to schedule sensors to watch targets and forward the sensed data to the base station, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched and all active sensors are connected to the base station. We propose an optimal solution to find the target-watching schedule for sensors that achieves the maximal lifetime. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using the linear programming technique; 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime; and 3) determining the sensor surveillance trees based on the above obtained schedule matrices, which specify the active sensors and the routes to pass sensed data to the base station. This is the first time in the literature that the problem of maximizing lifetime of sensor surveillance systems has been formulated and the optimal solution has been found.

References

[1]
{1} C.-Y. Chong and S. P. Kumar, "Sensor networks: Evolution, opportunities, and challenges," Proc. IEEE, vol. 91, no. 8, pp. 1247-1256, Aug. 2003.
[2]
{2} T. Yan, T. He, and J. A. Stankovic, "Differentiated surveillance for sensor networks," in Proc. 1st Int. Conf. Embedded Networked Sensor Systems, Los Angeles, CA, 2003, pp. 51-62.
[3]
{3} C.-F. Hsin and M. Liu, "A distributed monitoring mechanism for wireless sensor networks," in Proc. Int. Conf. Mobile Computing and Networking, ACM Workshop on Wireless Security, Atlanta, GA, 2002, pp. 57-66.
[4]
{4} Y. Zhao, R. Govindan, and D. Estrin, "Residual energy scans for monitoring wireless sensor networks," in Proc. IEEE Wireless Communications and Networking Conf., 2002, pp. 356-362.
[5]
{5} S. Mao and Y. T. Hou, "BeamStar: A new low-cost data routing protocol for wireless sensor networks," presented at the IEEE Globecom, Dallas, TX, 2004.
[6]
{6} W. Choi and S. K. Das, "Trade-off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks," presented at the 1st IEEE Int. Conf. Mobile Ad Hoc and Sensor Systems (MASS 2004), Fort Lauderdale, FL, Oct. 2004.
[7]
{7} C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: A scalable and robust communication paradigm for sensor networks," presented at the 6th Annu. ACM/IEEE Int. Conf. Mobile Computing and Networking (MOBICOM), Boston, MA, Aug. 2000.
[8]
{8} W. Heinzelman, A. Chandrakasan, and H. Balakrishna, "Energy-efficient communication protocol for wireless microsensor networks," presented at the 33rd Annu. Hawaii Int. Conf. System Sciences (HICSS- 33), Maui, HI, Jan. 2000.
[9]
{9} S. Lindsey, C. Raghavendra, and K. M. Sivalingam, "Data gathering algorithms in sensor networks using energy metrics," IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 9, pp. 924-935, Sep. 2002.
[10]
{10} N. Sadagopan and B. Krishnamachari, "ACQUIRE: The acquire mechanism for efficient querying in sensor networks," in Proc. 1st IEEE Int. Workshop on Sensor Network Protocols and Application (SNPA), 2003, pp. 149-155.
[11]
{11} W. R. Heinzelman, J. Kulit, and H. Balakrishnan, "Adaptive protocols for information dissemination in wireless sensor networks," presented at the 5th ACM/IEEE Annu. Int. Conf. Mobile Computing and Networking (MOBICOM), Seattle, WA, Aug. 1999.
[12]
{12} M. Bhardwaj, T. Garnett, and A. Chandrakasan, "Upper bounds on the lifetime of sensor networks," in IEEE Int. Conf. Communications, 2001, pp. 785-790.
[13]
{13} J. Chang and L. Tassiulas, "Maximum lifetime routing in wireless sensor networks," presented at the Advanced Telecommunications and Information Distribution Research Program (ATIRP'2000), College Park, MD, Mar. 2000.
[14]
{14} T. Melodia, D. Pompili, and I. F. Akyildiz, "Optimal local topology knowledge for energy efficient geographical routing in sensor networks," in Proc. IEEE INFOCOM, 2004, pp. 1705-1716.
[15]
{15} N. Sadagopan and B. Krishnamachari, "Maximizing data extraction in energy-limited sensor networks," in Proc. IEEE INFOCOM, 2004, pp. 1717-1727.
[16]
{16} G. Zussman and A. Segall, "Energy efficient routing in ad hoc disaster recovery networks," in Proc. IEEE INFOCOM, 2003, pp. 682-691.
[17]
{17} J. Carle and D. Simplot-Ryl, "Energy-efficient area monitoring for sensor networks," IEEE Computer, vol. 37, no. 2, pp. 40-46, Feb. 2004.
[18]
{18} C. F. Chiasserini and M. Garetto, "Modeling the performance of wireless sensor networks," in Proc. IEEE INFOCOM, 2004, pp. 220-231.
[19]
{19} D. Tian and N. D. Georganas, "A coverage-preserving node scheduling scheme for large wireless sensor networks," in Proc. 1st ACM Int. Workshop on Wireless Sensor Networks and Applications, 2002, pp. 32-41.
[20]
{20} L. B. Ruiz et al., "Scheduling nodes in wireless sensor networks: A Voronoi approach," in Proc. 28th IEEE Conf. Local Computer Networks (LCNS2003), Bonn/Konigswinter, Germany, Oct. 2003, pp. 423-429.
[21]
{21} A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, "Wireless sensor networks for habitat monitoring," in Proc. 1st ACM Int. Workshop on Wireless Sensor Networks and Applications, Atlanta, Ga, Sep. 2002, pp. 88-97.
[22]
{22} H. J. Ryser, Combinational Mathematics. Washington, DC: The Mathematical Association of America, 1963, pp. 58-59.
[23]
{23} R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory. Cambridge, U.K.: Cambridge Univ. Press, 1991, pp. 9-10.
[24]
{24} D. B. West, Introduction to Graph Theory. Englewood Cliffs, NJ: Prentice-Hall, 1996, pp. 109-111.
[25]
{25} S. Axler, F. W. Gehring, and K. A. Ribet, Graph Theory, 2nd ed. New York: Springer, 2000.
[26]
{26} R. Gould, Graph Theory. Boston, MA: Benjamin/Cummings, 1988, pp. 198-209.
[27]
{27} K. Römer, "Time synchronization in ad hoc networks," presented at the ACM Mobihoc, Long Beach, CA, 2001.
[28]
{28} Q. Li and D. Rus, "Global clock synchronization in sensor networks," in Proc. IEEE INFOCOM, 2004, pp. 214-226.
[29]
{29} A. Savvides, C.-C. Han, and M. Srivastava, "Dynamic fine-grained localization in ad hoc networks of sensors," in Proc. MobiCom 2001, Rome, Italy, 2001, pp. 166-179.
[30]
{30} Z. Zhou, S. R. Das, and H. Gupta, "Connected K-coverage problem in sensor networks," in Proc. ICCCN 2004, pp. 373-378.
[31]
{31} H. Liu, P. Wan, C.-W. Yi, X. Jia, S. Makki, and P. Niki, "Maximal lifetime scheduling in sensor surveillance networks," in Proc. IEEE INFOCOM, Miami, FL, 2005, pp. 2482-2491.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 2
April 2007
232 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2007
Published in TON Volume 15, Issue 2

Author Tags

  1. energy efficiency
  2. lifetime
  3. scheduling
  4. sensor network
  5. surveillance system

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Rest with eyes openInternational Journal of Sensor Networks10.1504/IJSNET.2016.07425420:1(16-25)Online publication date: 1-Jan-2016
  • (2016)Partial target coverage to extend the lifetime in wireless multi-role sensor networksNetworks10.1002/net.2168268:1(34-53)Online publication date: 1-Aug-2016
  • (2013)Energy-efficient data dissemination using beamforming in wireless sensor networksACM Transactions on Sensor Networks10.1145/2480730.24807349:3(1-30)Online publication date: 4-Jun-2013
  • (2013)Systematic investigation of the effects of unidirectional links on the lifetime of wireless sensor networksComputer Standards & Interfaces10.1016/j.csi.2013.07.00536:1(132-142)Online publication date: 1-Nov-2013
  • (2013)Lifetime maximization considering target coverage and connectivity in directional image/video sensor networksThe Journal of Supercomputing10.1007/s11227-011-0646-965:1(365-382)Online publication date: 1-Jul-2013
  • (2011)Coverage problems in sensor networksACM Computing Surveys10.1145/1978802.197881143:4(1-53)Online publication date: 18-Oct-2011
  • (2011)Maximum lifetime coverage preserving scheduling algorithms in sensor networksJournal of Global Optimization10.1007/s10898-010-9636-351:3(447-462)Online publication date: 1-Nov-2011
  • (2010)Energy-efficient algorithm for the target Q-coverage problem in wireless sensor networksProceedings of the 5th international conference on Wireless algorithms, systems, and applications10.5555/1881353.1881357(21-25)Online publication date: 15-Aug-2010
  • (2010)Survey on contemporary remote surveillance systems for public safetyIEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews10.1109/TSMCC.2010.204244640:5(493-515)Online publication date: 1-Sep-2010
  • (2010)Prolonging network lifetime with multi-domain cooperation strategies in wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2009.11.0048:6(582-596)Online publication date: 1-Aug-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media