Latency of wireless sensor networks with uncoordinated power saving mechanisms

ABSTRACT

We consider a wireless sensor network, where nodes switch between an active (on) and a sleeping (off) mode, to save energy. The basic assumptions are that the on/off schedules are completely uncoordinated and that the sensors are distributed according to a Poisson process and their connectivity ranges are larger or equal to their sensing ranges. Moreover, the durations of active and sleeping periods are such that the number of active nodes at any particular time is so low that the network is always disconnected.Is it possible to use such a network for time-critical monitoring of an area? Such a scenario requires indeed to have bounds on the latency, which is the delay elapsed between the time at which an incoming event is sensed by some node of the network and the time at which this information is retrieved by the data collecting sink. A positive answer is provided to this question under some simplifying assumptions discussed in the paper. More precisely, we prove that the messages sent by a sensing node reach the sink with a fixed asymptotic speed, which does not depend on the random location of the nodes, but only on the network parameters (node density, connectivity range, duration of active and sleeping periods). The results are obtained rigorously by using an extension of first passage percolation theory.

REFERENCES

• 1: François Baccelli , Bartłomiej Błaszczyszyn , Florent Tournois, Spatial averages of coverage characteristics in large CDMA networks, Wireless Networks, v.8 n.6, p.569-586, November 2002 [doi>10.1023/A:1020321501945]
• 2: J. van den Berg, R. Meester, and D.G. White. Dynamic Boolean models. Stochastic Processes and their Applications, 69:247--257, 1997.
• 3: J.-H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings of IEEE Infocom 2000, pages 22--31, Jerusalem, 2000.
• 4: C.-F. Chiasserini and M. Garetto. Modeling the performance of wireless sensor networks. In Proceedings of IEEE Infocom 2004, 2004.
• 5: M. Deijfen. Asymptotic shape in a continuum growth model. Advances in Applied Probability, 35(2):303--318, 2003.
• 6: M. Deijfen, O. Häggström, and J. Bagley. A stochastic model for competing growth on ℝd. Markov Processes and Related Fields, 2003.
• 7: Olivier Dousse , François Baccelli , Patrick Thiran, Impact of interferences on connectivity in ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.425-436, April 2005 [doi>10.1109/TNET.2005.845546]
• 8: A. El Gamal, C. Nair, B. Prabhakar, E. Uysal-Biyikoglu, and S. Zahedi. Energy-efficient scheduling of packet transmissions over wireless networks. In Proceedings of IEEE Infocom 2002, pages 1773--1782, 2001.
• 9: A. Ephremides. Energy concerns in wireless networks. IEEE Wireless Communications, 9(4):48--59, 2002.
• 10: M. Franceschetti, L. Booth, J. Bruck, M. Cook, and R. Meester. Percolation in multi-hop wireless networks. IEEE Transaction on Information Theory, 2003. Submitted. A short version appeared at ISIT'03.
• 11: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical Report UCLA/CSD-TR 02-0013, UCLA, 2002.
• 12: G. Grimmett. Percolation, volume 321 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2nd edition, 1999.
• 13: G. Grimmett and J. Marstrand. The supercritical phase of percolation is well behaved. Proc. Royal Soc. London Ser. A, 430:439--457, 1990.
• 14: O. Häggström, Y. Peres, and J. Steif. Dynamic percolation. Ann. IHP Probab. et. Statist., 33:497--528, 1997.
• 15: B. Krishanamachari, D. Estrin, and S. Wicker. The impact of data aggregation in wireless sensor networks. In Proc. of International Workshop of Distributed Event Based Systems (DEBS), Vienna, Austria, 2002.
• 16: T. Liggett. An improved subadditive ergodic theorem. The Annals of Probability, 13(4):1279--1285, 1985.
• 17: B. Liu and D. Towsley. On the coverage and detectability of wireless sensor networks. In Proceedings of WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, 2003.
• 18: R. Meester and R. Roy. Continuum percolation, volume 119 of Cambridge tracts in mathematics. Cambridge University Press, 1996.
• 19: Y. Peres and J. Steif. The number of infinite clusters in dynamical percolation. Probab. Th. Rel. Fields, 111:141--165, 1998.
• 20: B. Prabhakar, E. Uysal-Biyikoglu, and A. El Gamal. Energy-efficient transmission over a wireless link via lazy packet scheduling. In Proceedings of IEEE Infocom 2001, pages 386--394, 2001.
• 21: J. Quintanilla, S. Torquato, and R.M. Ziff. Efficient measurement of the percolation threshold for fully penetrable discs. J. Phys. A, 33:399--407, 2000.
• 22: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 23: Amit Sinha , Anantha Chandrakasan, Dynamic Power Management in Wireless Sensor Networks, IEEE Design & Test, v.18 n.2, p.62-74, March 2001 [doi>10.1109/54.914626]
• 24: D. Stoyan, W.S. Kendall, and J. Mecke. Stochastic geometry and its applications. Wiley, Chichester, 2nd edition, 1995.
• 25: T. Vicsek and J. Kertesz. Monte Carlo renormalisation group approach to percolation on a continuum: Test of universality. J. Phys. A, 14(L31), 1981.
• 26: Y. Wei, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proc. IEEE Infocom, New York, June 2002.
• 27: W. Ye and J. Heidemann. Medium access control in wireless sensor networks. Technical Report ISI-TR-580, USC, 2003.
• 28: Y. Yu, B. Krishnamachari, and V. Prasanna. Energy-latency tradeoffs for data gathering in wireless sensor networks. In Proceedings of IEEE Infocom 2004, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Performance, Theory

Keywords:
continuum percolation, first passage percolation, sensor networks