Maximizing lifetime of sensor surveillance systems

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: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958498]
• 3: Chih-fan Hsin , Mingyan Liu, A distributed monitoring mechanism for wireless sensor networks, Proceedings of the 1st ACM workshop on Wireless security, p.57-66, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570688]
• 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: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 8: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 9: Stephanie Lindsey , Cauligi Raghavendra , Krishna M. Sivalingam, Data Gathering Algorithms in Sensor Networks Using Energy Metrics, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.924-935, September 2002 [doi>10.1109/TPDS.2002.1036066 ]
• 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: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 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: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 20: Marcos Augusto M. Vieira , Luiz Filipe M. Vieira , Linnyer B. Ruiz , Antonio A. F. Loureiro , Antonio O. Fernandes , José Marcos S. Nogueira, Scheduling Nodes in Wireless Sensor Networks: A Voronoi Approach, Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, p.423, October 20-24, 2003
• 21: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 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: Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
• 28: [28] Q. Li and D. Rus, "Global clock synchronization in sensor networks," in Proc. IEEE INFOCOM, 2004, pp. 214-226.
• 29: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Management

Keywords:
energy efficiency, lifetime, scheduling, sensor network, surveillance system