Lifetime maximization for connected target coverage in wireless sensor networks

ABSTRACT

In this paper, we consider the connected target coverage (CTC) problem with the objective of maximizing the network lifetime by scheduling sensors into multiple sets, each of which can maintain both target coverage and connectivity among all the active sensors and the sink.We model the CTC problem as a maximum cover tree (MCT) problem and prove that the MCT problem is NP-Complete. We determine an upper bound on the network lifetime for the MCT problem and then develop a (1+w) H (M) approximation algorithm to solve it, where is an arbitrarily small number, H(M) = Σ1≤i≤M (1/i) and M is the maximum number of targets in the sensing area of any sensor. As the protocol cost of the approximation algorithm may be high in practice, we develop a faster heuristic algorithm based on the approximation algorithm called Communication Weighted Greedy Cover (CWGC) algorithm and present a distributed implementation of the heuristic algorithm. We study the performance of the approximation algorithm and CWGC algorithm by comparing them with the lifetime upper bound and other basic algorithms that consider the coverage and connectivity problems independently. Simulation results show that the approximation algorithm and CWGC algorithm perform much better than others in terms of the network lifetime and the performance improvement can be up to 45% than the best-known basic algorithm. The lifetime obtained by our algorithms is close to the upper bound. Compared with the approximation algorithm, the CWGC algorithm can achieve a similar performance in terms of the network lifetime with a lower protocol cost.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: M. Cardei and J. Wu, "Coverage problems in wireless ad hoc sensor networks," in Handbook of Sensor Networks, M. Ilyas and I. Mahgoub, Eds. Boca Raton, FL: CRC Press, 2004, ch. 19.
• 3: C.-F. Huang and Y.-C. Tseng, "A survey of solutions to the coverage problems in wireless sensor networks," J. Internet Technol., vol. 6, no. 1, pp. 1-8, 2005.
• 4: S. Slijepcevic and M. Potkonjak, "Power efficient organization of wireless sensor networks," in Proc. IEEE Int. Conf. Communications (ICC), Jun. 2001, vol. 2, pp. 472-476.
• 5: Mihaela Cardei , Ding-Zhu Du, Improving wireless sensor network lifetime through power aware organization, Wireless Networks, v.11 n.3, p.333-340, May 2005 [doi>10.1007/s11276-005-6615-6]
• 6: M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-efficient target coverage in wireless sensor networks," in Proc. IEEE INFOCOM, 2005, pp. 1976-1984.
• 7: M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz, "Maximum network lifetime in wireless sensor networks with adjustable sensing ranges," in IEEE Int. Conf. Wireless and Mobile Computing, Networking and Communications (WiMob), 2005.
• 8: M. Lu, J. Wu, M. Cardei, and M. Li, "Energy-efficient connected coverage of discrete targets in wireless sensor netorks," in Int. Conf. Computer Networks and Mobile Computing (ICCNMC), 2005.
• 9: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless 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.958496]
• 10: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 11: V. Vhvatal, "A greedy heuristic for the set-covering problem," Math. Oper. Res., vol. 4, no. 3, pp. 233-235, 1979.
• 12: Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004 [doi>10.1109/TNET.2004.833122]
• 13: M. Cardei and J. Wu, "Energy-efficient coverage problems in wireless ad hoc sensor networks," Computer Commun., vol. 29, no. 4, pp. 413-420, 2006.
• 14: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Coverage problems in wireless ad hoc sensor networks," in IEEE INFOCOM 2001.
• 15: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 16: H. Zhang and J. C. Hou, Maintaining Sensing Coverage and Connectivity in Large Sensor Networks Dept. Computer Sci., Univ. of Illinois at Urbana-Champaign, Tech. Rep., 2003.
• 17: P. Berman, G. Calinescu, C. Shah, and A. Zelikovsky, "Power efficient monitoring management in sensor networks," in WCNC 2004.
• 18: M. Cardei, D. MacCallum, X. Cheng, M. Min, X. Jia, D. Li, and D.-Z. Du, "Wireless sensor networks with energy efficient organization," J. Interconnection Netw., vol. 3, no. 3, pp. 213-229, 2002.
• 19: Z. Zhou, S. Das, and H. Gupta, "Connected k-coverage problem in sensor networks," in Proc. 13th Int. Conf. Computer Communications and Networks (ICCCN), 2004, pp. 373-378.
• 20: 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]
• 21: Himanshu Gupta , Zongheng Zhou , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.55-67, February 2006 [doi>10.1109/TNET.2005.863478]
• 22: Yuzhen Liu , Weifa Liang, Approximate Coverage in Wireless Sensor Networks, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.68-75, November 15-17, 2005 [doi>10.1109/LCN.2005.32]
• 23: L. Wang and S. S. Kulkarni, "Pcover: Partial coverage for long-lived surveillance sensor networks," Dept. Computer Sci. Eng., Michigan State Univ., Tech. Rep. MSC-CSE-0530, 2005.
• 24: Zoë Abrams , Ashish Goel , Serge Plotkin, Set k-cover algorithms for energy efficient monitoring in wireless sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984684]
• 25: Q. Zhao and M. Gurusamy, "Lifetime maximization using observation time scheduling in multi-hop sensor networks," in IEEE/CreateNetw Int. Workshop on Broadband Advanced Sensor Networks (BroadNets), 2005.
• 26: M. Bhardwaj and A. P. Chandrakasan, "Bounding the lifetime of sensor networks via optimal role assignments," in Proc. IEEE INFOCOM, 2002, vol. 3, pp. 1587-1596.
• 27: K. Kalpakis, K. Dasgupta, and P. Namjoshi, "Maximum lifetime data gathering and aggregation in wireless sensor networks," Computer Sci. Electr. Eng. Dept., Univ. of Maryland, Baltimore, Tech. Rep., 2002.
• 28: N. Sadagopan and B. Krishnamachari, "Maximizing data extraction in energy-limited sensor networks," in Proc. IEEE INFOCOM, 2004, vol. 3, pp. 1717-1727.
• 29: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 30: George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
NP-complete, approximation algorithms, coverage, network lifetime, sensor activity scheduling, wireless sensor networks