Distributed energy management algorithm for large-scale wireless sensor networks

ABSTRACT

In battery-constrained wireless sensor networks, it is important to employ effective energy management while maintaining some level of network connectivity. Viewing this problem from a percolation-based connectivity perspective, we propose a fully distributed energy management algorithm for large-scale wireless sensor networks. This algorithm allows each sensor to probabilistically schedule its own activity based on its node degree. This mechanism is modelled by a degree-dependent dynamic site percolation process on random geometric graphs. We specify the conditions under which the resulting network is guaranteed to be percolated at all the time. We further study the delay performance of the proposed energy management algorithm by modelling the problem as a degree-dependent first passage percolation process on random geometric graphs.

REFERENCES

• 1: Eugene Shih , Paramvir Bahl , Michael J. Sinclair, Wake on wireless: an event driven energy saving strategy for battery operated devices, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570666]
• 2: G. Lu, N. Sadagopan, B. Krishanamachari, and A. Goel, "Delay eficient sleep scheduling in wireless sensor networks," in Proc. IEEE INFOCOM'05, 2005.
• 3: 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]
• 4: Rong Zheng , Jennifer C. Hou , Lui Sha, Asynchronous wakeup for ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778420]
• 5: G. Grimmett, Percolation. New York: Springer, second ed., 1999.
• 6: R. Meester and R. Roy, Continuum Percolation. New York: Cambridge University Press, 1996.
• 7: M. Penrose, Random Geometric Graphs. New York: Oxford, University Press, 2003.
• 8: P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, pp. 547--566, 1998.
• 9: L. Booth, J. Bruck, M. Franceschetti, and R. Meester, "Covering algorithms, continuum percolation and the geometry of wireless networks," Annals of Applied Probability, vol. 13, pp. 722--741, May 2003.
• 10: M. Franceschetti, L. Booth, M. Cook, J. Bruck, and R. Meester, "Continuum percolation with unreliable and spread out connections," Journal of Statistical Physics, vol. 118, pp. 721--734, Feb. 2005.
• 11: Olivier Dousse , Petteri Mannersalo , Patrick Thiran, Latency of wireless sensor networks with uncoordinated power saving mechanisms, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989474]
• 12: O. Dousse, M. Franceschetti, and P. Thiran, "Information theoretic bounds on the throughput scaling of wireless relay networks," in Proc. IEEE INFOCOM'05, Mar. 2005.
• 13: 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]
• 14: O. Dousse, M. Franceschetti, N. Macris, R. Meester, and P. Thiran, "Percolation in the signal to interference ratio graph," Journal of Applied Probability, vol. 43, no. 552--562, 2006.
• 15: T. Liggett, "An improved subadditive ergodic theorem," Annals of Prob., vol. 13, pp. 1279--1285, 1985.
• 16: J. Quintanilla, S. Torquato, and R. M. Ziff, "Efficient measurement of the percoaltion threshold for fully penetrable discs," Physics A, vol. 86, pp. 399--407, 2000.
• 17: P. Hall, "On continuum percolation," Annals of Prob., vol. 13, pp. 1250--1266, 1985.
• 18: Z. Kong and E. M. Yeh, "Analytical lower bounds on the critical density in continuum percolation," in Proc. of the Workshop on Spatial Stochastic Models in Wireless Networks (SpaSWiN), April 2007.
• 19: Z. Kong and E. M. Yeh, "Characterization of the critical density for percolation in random geometric graphs." to appear in Proc. of 2007 IEEE International Symposium on Information Theory, June 2007.
• 20: P. Brighten Godfrey , David Ratajczak, Naps: scalable, robust topology management in wireless ad hoc networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984686]
• 21: O. Häggström, Y. Peres, and J. E. Steif, "Dynamic percolation," Ann. IHP Prob. et. Stat., vol. 33, pp. 497--528, 1997.
• 22: H. Kesten, "Percolation theory and first passage percolation," Annals of Prob., vol. 15, pp. 1231--1271, 1987.
• 23: M. Deijfen, "Asymptotic shape in a continuum growth model," Adv. in Applied Prob., vol. 35, pp. 303--318, 2003.
• 24: R. Durret, Probability: Theory and Examples. Duxbury Press, 2nd ed., 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Performance, Theory

Keywords:
dependent dynamic percolation, first passage percolation, subadditive ergodic theorem