Set k-cover algorithms for energy efficient monitoring in wireless sensor networks

ABSTRACT

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in [13], where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1-1<over>e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1<over>2 approximation ratio and the other is a centralized greedy algorithm with a 1-1<over>e approximation ratio. We show that it is NP-Complete to guarantee better than 15<over>16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible in polynomial time, assuming P ≠ NP. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.

REFERENCES

• 1: National Research Council Staff, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Academy Press, Washington, DC, 2001
• 2: L. Benini , G. Castelli , A. Macii , E. Macii , M. Poncino , R. Scarsi, A discrete-time battery model for high-level power estimation, Proceedings of the conference on Design, automation and test in Europe, p.35-41, March 27-30, 2000, Paris, France [doi>10.1145/343647.343694]
• 3: Bonnie Berger , Jon Kleinberg , Tom Leighton, Reconstructing a three-dimensional model with arbitrary errors, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.449-458, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237993]
• 4: F. Bian, A. Goel, C. Raghavendra, and X. Li. Energy-efficient broadcast in wireless ad hoc networks: lower bounds and algorithms. In Journal of Interconnection Networks, 3(3-4), pp 149--166, September 2002.
• 5: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 6: Venkatesan Guruswami, Inapproximability results for set splitting and satisfiability problems with no mixed clauses, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.155-166, September 05-08, 2000
• 7: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 8: A. Howard, M. Mataric, and G. Sukhatme. Relocation on a mesh: A formalism for generalized localization. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Wailea, Hawaii, Oct. 2001.
• 9: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 10: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 11: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 12: C. Savarese, J. Rabaey, and J. Beutel. Locationing in Distributed Ad-Hoc Wireless Sensor Networks. In Proceedings of ICASSP Salt Lake City, pp.2037--2040, UT May 2001.
• 13: S. Slijepcevic and M. Potkonjak. Power Efficient Organization of Wireless Sensor Networks. IEEE International Conference on Communications (ICC), Helsinki, Finland, June 2001.
• 14: D. Tian, and N.D. Georganas. A Node Scheduloing Scheme for Energy Condervation in Large Wireless Sensor Networks. In, Wireless Communications and Mobile Computing Journal, May 2003.
• 15: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 16: J. Warrior. Smart Sensor Networks of the Future. In Sensors Magazine, March 1997.
• 17: D. Wolpert, and W. Macready. No Free Lunch Theorems for Optimization. In IEEE Transactions on Evolutionary Computation, 1996.
• 18: 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]
• 19: F. Ye, G. Zhong, S. Lu, and L. Zhang. Energy Efficient Robust Sensing Coverage in Large Sensor Networks. UCLA Technical Report, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
analysis of algorithms, energy conservation, wireless sensor networks