Optimally balancing energy consumption versus latency in sensor network routing

ABSTRACT

We consider wireless sensor networks with nodes switching ON (awake) and OFF (sleeping) to preserve energy, and transmitting data over channels with varying quality. The objective is to determine the best path from each node to a single gateway. The performance metrics we are interested in are: the expected energy consumption, and the probability that the latency exceeds a certain threshold. Under Markovian assumptions on the sleeping schedules and the channel conditions, we obtain the expected energy consumption of transmitting a packet on any path to the gateway. We also provide an upper (Chernoff) bound and a tight large deviations asymptotic for the latency probability on each path. To capture the trade-off between energy consumption and latency probability, we formulate the problem of choosing a path to minimize a weighted sum of the expected energy consumption and the exponent of the latency probability. We provide two algorithms to solve this problem: a centralized stochastic global optimization algorithm, and a distributed algorithm based on simulated annealing. The proposed methodology can also optimize over the fraction of time that sensor nodes remain ON (duty cycle).

REFERENCES

• 1: Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
• 2: Bertsekas, D. 1999. Nonlinear Programming, 2nd ed. Athena Scientific, Belmont, MA.
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: Bhattacharya, R. N. and Waymire, E. C. 1990. Stochastic Processes with Applications. Wiley Series in Probability and Mathematical Statistics.
• 5: 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]
• 6: Elliot, E. O. 1963. Estimates of error rates for codes on burst-noise channels. Bell Systems Tech. J. 42, 1977--1997.
• 7: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 8: Sinem Coleri Ergen , Pravin Varaiya, PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks, IEEE Transactions on Mobile Computing, v.5 n.7, p.920-930, July 2006 [doi>10.1109/TMC.2006.100]
• 9: Fuemmeler, J. and Veeravalli, V. V. 2007. Smart sleeping policies for energy efficient tracking in sensor networks. IEEE Trans. Signal Proc. 56, 5, 2091--2101.
• 10: 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
• 11: Gilbert, E. N. 1960. Capacity of a burst-noise channel. Bell Systems Tech. J. 39, 1253--1266.
• 12: 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
• 13: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 14: Almudena Konrad , Ben Y. Zhao , Anthony D. Joseph , Reiner Ludwig, A Markov-based channel model algorithm for wireless networks, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.28-36, July 2001, Rome, Italy [doi>10.1145/381591.381602]
• 15: Lu, G., Sadagopan, N., Krishnamachari, B., and Goel, A. 2005. Delay efficient sleep scheduling in wireless sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05). Vol. 14. 2470--2481.
• 16: Magnani, A., Lall, S., and Boyd, S. 2005. Tractable fitting with convex polynomials via sum-of-squares. In Proceedings of the 43rd Conference on Decision and Control, 1672--1677.
• 17: 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]
• 18: Miao, L. and Cassandras, C. G. 2006. Optimal transmission scheduling for energy-efficient wireless networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'06).
• 19: Paschalidis, I. C., Shen, Y., Vakili, P., and Vajda, S. 2007. SDU: a semi-definite programming-based underestimation method for stochastic global optimization in protein docking. IEEE Trans. Automat. Contr. 52, 4, 664--676.
• 20: Saikat Ray , Wei Lai , Ioannis Ch. Paschalidis, Statistical location detection with sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2670-2683, June 2006 [doi>10.1109/TIT.2006.874376]
• 21: Wang, H. S. and Moayeri, N. 1995. Finite-state Markov channel-a useful model for radio communication channels. IEEE Trans. Veh. Tech. 44, 163--171.
• 22: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]
• 23: Wei Ye , John Heidemann , Deborah Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.493-506, June 2004 [doi>10.1109/TNET.2004.828953]
• 24: Yu, Y., Krishnamachari, B., and Prasanna, V. K. 2004. Energy-latency tradeoff for data gathering in wireless sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04). Vol. 1. p. 255.
• 25: Zhang, Q. and Kassam, K. 1999. Finite-state Markov model for Rayleigh fading channels. IEEE Trans. on Comm. 47, 11, 1688--1692.

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization; Nonlinear programming
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Performance

Keywords:
Sensor networks, energy and resource management, latency, routing, sleeping schedule