Energy-efficient routing for signal detection under the Neyman-Pearson criterion in wireless sensor networks

ABSTRACT

Energy-efficient routing for wireless sensor networks (WSNs) has been a topic of great interest for the last few years, but thus far routing for signal detection in WSNs has not attracted much attention. In particular, little research has focused on the Neyman-Pearson criterion which is the most well accepted metric for radar, sonar and related signal detection problems. In this paper, we formulate the problem of energy-efficient routing for signal detection under the Neyman-Pearson criterion, apparently for the first time. We hereby propose two different routing metrics that aim at a tradeoff between the detection performance and the energy consumption. In particular, the first one leads to a combinatorial problem of identifying a path which achieves the largest possible mean detection-probability-to-energy ratio, while the second one reduces to finding a route which minimizes the consumed energy while maintaining a predeter-mined detection probability. We further provide efficient algorithms for solving these problems based on state-of-the-art research from operations research. We also present simulation results which indicate the distinctive energy-performance balance achieved by each proposed routing metric.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, pp. 102--114, August 2002.
• 2: B. M. Sadler, "Fundamentals of energy-constrained sensor network systems," IEEE Aerospace and Electronic Systems Magazine, vol. 20, pp. 17--35, August 2005.
• 3: R. Viswanathan and P. K. Varshney, "Distributed detection with multiple sensors: part I-fundamentals," Proceedings of the IEEE, vol. 85, pp. 54--63, January 1997.
• 4: R. S. Blum, S. A. Kassam, and H. V. Poor, "Distribued detection with multiple sensors: part II-advanced topics," Proceedings of the IEEE, vol. 85, pp. 64--79, January 1997.
• 5: J.-F. Chamberland and V. V. Veeravalli, "Decentralized detection in sensor networks," IEEE Transactions on Signal Processing, vol. 51, pp. 407--416, February 2003.
• 6: Q. Cheng, B. Chen, and P. K. Varshney, "Detection performance limits for distributed sensor networks in the presence of non-ideal channels," to appear in IEEE Transactions on Wireless Communications.
• 7: J. N. Al-Karaki and A. E. Kamal, "Routing techniques in wireless sensor networks: a survey," IEEE Wireless Communications, pp. 6--28, December 2004.
• 8: 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]
• 9: S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin, and A. O. Fapojuwo, "A centralized energy-efficient routing protocol for wireless sensor networks," IEEE Communications Magazine, pp. S8--13, vol. 43, March 2005.
• 10: J. Liu, F. Zhao, and D. Petrovic, "Information-directed routing in ad hoc sensor networks," IEEE Journal on Selected Areas in Communications, pp. 851--861, vol. 23, April 2005.
• 11: Y. Sung, S. Misra, L. Tong, and A. Ephremides, "Cooperative routing for distributed detection in large sensor networks," to appear in IEEE Journal on Selected Areas in Communications, 2007.
• 12: H. Vincent Poor, An introduction to signal detection and estimation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 13: M. I. Skolnik, Ed., Radar Handbook, McGraw-Hill, New York, 2nd Edition, 1990.
• 14: Micropower Impulse Radar, Science & Technology Review, pp. 16--29, January/February 1996.
• 15: Prabal K. Dutta , Anish K. Arora , Steven B. Bibyk, Towards radar-enabled sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127848]
• 16: Z. Tu and R. S. Blum, "On the limitations of random sensor placement for distributed signal detection," in Proceedings of IEEE International Conference on Communications (ICC), Glasgow, UK, 2007.
• 17: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 18: E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holts, Rinehart and Winston, New York, 1976.
• 19: M. Hartmann and J. B. Orlin, "Finding minimum cost to time ratio cycles with small integral transit times," Networks, vol. 23, pp.567--74, 1993.
• 20: P. C. T. Tung, "Finding a minimal-ratio elementary path in a network," Asia-Pacific Journal of Operational Research, vol. 3, pp. 151--157, November 1987.
• 21: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 22: A. V. Goldberg and T. Radzik, "A heuristic improvement of the Bellman-Ford algorithm," Applied Mathematics Letters, vol. 6, pp. 3--6, 1993.
• 23: B. V. Cherkassky and A. V. Goldberg, "Negative-cycle detection algorithms," Mathematical Programming, vol. 85, pp. 277--311, 1999.
• 24: F. Kuipers, P. V. Mieghem, T. Korkmaz, and M. Krunz, "An overview of constraint-based path selection algorithms for Qos routing," IEEE Communications Magazine, vol. 40, pp. 50--55, December 2002.
• 25: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 26: I. Dumitrescu and N. Boland, "Algorithms for the weight constrained shortest path problem," International Transactions in Operational Research, vol. 8, pp. 15--29, 2001.
• 27: G. Handler and I. Zang, "A dual algorithm for the constrained shortest path problem," Networks, vol. 10, pp. 293--310, 1980.
• 28: M. Minoux and C. C. Ribeiro, "Solving hard constrained shortest path problems by lagrangean relaxation and branch-and-bound algorithms," Methods of Operations Research, vol. 53, pp. 305--316, 1986.
• 29: J. E. Beasley and N. Christofides, "An algorithm for the resource constrained shortest path problem," Networks, vol. 19, pp. 379--394, 1989.
• 30: W. M. Carlyle and R. K. Wood, "Lagrangian relaxation and enumeration for solving constrained shortest-path problems," in Proceedings of the 38th Annual Conference of the Operational Research Society of New Zealand (ORSNZ), pp. 3--12, Hamilton, NZ, November 2003.
• 31: M. Ziegelmann, Constrained Shotest Paths and Related Problems, PhD thesis, Max-Planck-Institut für Informatik, Germany, 2001.
• 32: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 33: Y. Yang and R. S. Blum, "Routing for emitter/re ector signal detection in wireless sensor network systems," in Proceedings of IEEE International Conference on Communications (ICC), Glasgow, UK, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  H. Information Systems
  H.1 MODELS AND PRINCIPLES

General Terms:
Algorithms, Design, Performance

Keywords:
Neyman-Pearson criterion, active sensing, combinatorial optimization, energy efficiency, in-network processing, passive sensing, routing, signal detection, wireless sensor networks