On the critical phase transition time of wireless multi-hop networks with random failures

ABSTRACT

In this paper, we study the critical phase transition time of large-scale wireless multi-hop networks when the network topology experiences a partition due to increasing random node failures. We first define two new metrics, namely the last connection time and first partition time. The former is the last time that the network keeps a majority of surviving nodes connected in a single giant component; while the latter is the first time that the remaining surviving nodes are partitioned into multiple small components. Then we analyze the devolution process in a geometric random graph of n nodes based on percolation-theory connectivity and obtain the sufficient condition under which the graph is percolated. Based on the percolation condition, the last connection time and first partition time are found to be on the same order. Particularly, when the survival function of node lifetime is exponential, they are on the order of log(log n); while if the survival function is Pareto, the order is (log n)^1/ρ, where ρ is the shape parameter of Pareto distribution. Finally, simulation results confirm that the last connection time and first partition time serve as the lower and upper bounds of the critical phase transition time, respectively. Further, an interesting result is that the network with heavy-tailed survival functions is no more resilient to random failures than the network with light-tailed ones, in terms of critical phase transition time, if the expected node lifetimes are identical.

REFERENCES

• 1: P. Gupta and P.R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W.M. McEneaney et al, editors, Stochastic Analysis, Control, Optimization and Applications, pages 547--566. 1998.
• 2: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless 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.778431]
• 3: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 4: Peng-Jun Wan , Chih-Wei Yi, Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks, 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.989461]
• 5: R. Meester and R. Roy. Continuum Percolation. Cambridge University Press, 1996.
• 6: G. Grimmett. Percolation. Springer, 2 edition, 1999.
• 7: M. Penrose. Random Geometric Graphs. Oxford University Press, 2003.
• 8: B. Bollobas and O. Riordan. Percolation. Cambridge University Press, 2006.
• 9: R. Zheng. Information Dissemination in Power-constrained Wireless Networks. In Proc. of IEEE Infocom '06, Apr. 2006.
• 10: Xiang-Yang Li , Shao-Jie Tang , Ophir Frieder, Multicast capacity for large scale wireless ad hoc networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287886]
• 11: 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]
• 12: P. Gupta and P.R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 13: O. Dousse, M. Franceschetti, N. Macris, R. Meester, and P. Thiran. Percolation in the Signal to Interference Ratio Graph. Journal of Applied Probability, 43(2):552--562, 2006.
• 14: O. Dousse and P. Thiran. Connectivity vs Capacity in Dense Ad Hoc Networks. In Proc. of IEEE Infocom '04, Mar. 2004.
• 15: 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]
• 16: Zhenning Kong , Edmund M. Yeh, Distributed energy management algorithm for large-scale wireless sensor networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288136]
• 17: Paul Balister , Béla Bollobás_aff1n2 , Mark Walters_aff1n2, Continuum percolation with steps in the square or the disc, Random Structures & Algorithms, v.26 n.4, p.392-403, July 2005 [doi>10.1002/rsa.v26:4]
• 18: P.N. Balister, B. Bollobas, A. Sarkar, and M. Walters. Connectivity of Random K-nearest-neighbour Graphs. Advances in Applied Probability, 37(1):1--24, 2005.
• 19: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 20: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 21: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, A cone-based distributed topology-control algorithm for wireless multi-hop networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.147-159, February 2005 [doi>10.1109/TNET.2004.842229]
• 22: J. Dall and M. Christensen. Random Geometric Graphs. Physical Review E, 66(1):016121, Jul. 2002.
• 23: Ramin Hekmat, Ad-hoc Networks: Fundamental Properties and Network Topologies, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 24: B. Liang and Z.J. Haas. Predictive Distance-Based Mobility Management for PCS Networks. In Proc. of IEEE Infocom '99, Apr. 1999.
• 25: P. Nain, D. Towsley, B. Liu, and Z. Liu. Properties of Random Direction Models. In Proc. of IEEE Infocom '05, Mar. 2005.
• 26: Y.S. Chow and H. Teicher. Probability Theory: Independence, Interchangeability, Martingales. Springer, 3 edition, 1997.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Theory

Keywords:
continuum percolation, network devolution, phase transition time, random failures, wireless multihop networks