The bin-covering technique for thresholding random geometric graph properties

ABSTRACT

We study the emerging phenomenon of ad hoc, sensor-based communication networks. The communication is modeled by the geometric random graph model G(n, r, ℓ) where n points randomly placed within [0, ℓ]^d form the nodes, and any two nodes that correspond to points at most distance r away from each other are connected. We study fundamental properties of G(n, r, ℓ) of interest: connectivity, coverage, and routing-stretch. Our main contribution is a simple analysis technique we call bin-covering that we apply uniformly to get first known, (asymptotically) tight thresholds for each of these properties. Typically, in the past, geometric random graph analyses involved sophisticated methods from continuum percolation theory; on contrast, our bin-covering approach is discrete and very simple, yet it gives us tight threshold bounds. The technique also yields algorithmic benefits as illustrated by a simple local routing algorithm for finding paths with low stretch. Our specific results should also prove interesting to the networking community that has seen a recent increase in the study of geometric random graphs motivated by engineering ad hoc networks.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, Random evolution in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 2: N. Alon and J. Spencer. The Probabilistic Method, John Wiley, 2000.
• 3: D. Aldous. http://stat-www.berkeley.edu/users/aldous/Networks/, Spring 2003.
• 4: M. Appel and R. Russo. The connectivity of a graph on uniform points on {0, 1}d, Statistics and Probability Letters, 60, 351--357.
• 5: M. Appel and R. Russo. The Maximum Vertex Degree of a Graph on Uniform Points in {0, 1}d, Adv. Appl. Prob., 567--581, 1997.
• 6: M. Appel and R. Russo. The Minimum Vertex Degree of a Graph on Uniform Points in {0, 1}d, Adv. Appl. Prob., 582--594, 1997.
• 7: B. Bollobas. Random Graphs, Cambridge University Press, 2001.
• 8: J. Dall and M. Christensen. Random Geometric Graphs, Phys. Rev. E, 66(1): 016121, 9, 2002.
• 9: B. Deb, S. Bhatnagar and B. Nath. A topology discovery algorithm for sensor networks with applications to network management. Tech Report DCS-TR 441, Rutgers Univ., athos.rutgers.edu/dataman/papers.html, 2002.
• 10: L. Devroye. A Log Log Law for maximal uniform spacings. Ann. Probab., 26, 67-80, 1982.
• 11: Josep Díaz , Jordi Petit , Maria J. Serna, Random Geometric Problems on [0, 1]², Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.294-306, October 08-10, 1998
• 12: Josep Díaz , Mathew D. Penrose , Jordi Petit , Maria J. Serna, Linear Orderings of Random Geometric Graphs, Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, p.291-302, June 17-19, 1999
• 13: R. Ellis, J. Martin, and C. Yan. Random geometric graph diameter in the unit disk with ℓp metric, to appear in the 12th International Symposium on Graph Drawing, 2004.
• 14: R. Ellis, X. Jia, and C. Yan. On Random Points in the Unit Disk, http://www.math.tamu.edu/ rellis/, 2004.
• 15: Abraham Flaxman , Alan Frieze , Eli Upfal, Efficient communication in an ad-hoc network, Journal of Algorithms, v.52 n.1, p.1-7, July 2004 [doi>10.1016/j.jalgor.2004.01.004]
• 16: D. Ganesan, R. Govindan, S. Shenker and D. Estrin. Highly resilient, Energy-efficient Multipath Routing in Wireless Sensor Networks. Mobile Computing and Communication Review, Vol 1, No. 2, 2002.
• 17: Ashish Goel , Sanatan Rai , Bhaskar Krishnamachari, Sharp thresholds For monotone properties in random geometric graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007441]
• 18: P. Gupta and P. Kumar. Critical Power for Asympototic Connectivity in Wireless Networks, in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, W. M. McEneaney, G. Yin, and Q. Zhang (Eds.), Birkhuser, Boston, 1998.
• 19: P. Gupta and P. R. Kumar, The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2), 2000, pp. 388--404.
• 20: P. Hall. Introduction to the Theory of Coverage Processes, John Wiley, 1988.
• 21: P. Jaillet. On Properties of Geometric Random Graph Problems in the Plane, Annals of Operations Research, 61, 1--20, 1995.
• 22: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 23: J. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. The Web as a graph: Measurements, models and methods. Invited survey at the 5th Annual International Computing and Combinatorics conference (COCOON), 1999.
• 24: B. Krishnamachari, S. Wicker, R. Bejar and M. Pearlman. Critical density thresholds in distributed wireless networks. in Proc. of GLOBECOM, 2001. Enlarged version to appear in Communications, Information and Network Security, eds. H. Bhargava, H. V. Poor, V. Tarokh, and S. Yoon, Kluwer Publishers, 2002.
• 25: S. Meguerdichian, F. Koushanfar, M. Potkonjak and M. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proc. of INFOCOM 2001, 1380--1387.
• 26: R. Meester and R. Roy. Continuum Percolation, Cambridge University Press, 1996.
• 27: S. Muthukrishnan and G. Pandurangan. The Bincovering Technique for Thresholding Geometric Graph Properties, DIMACS Technical Report 2003-39, Nov. 2003.
• 28: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 29: M. D. Penrose. Random Geometric Graphs, Oxford University Press, 2003.
• 30: M. D. Penrose. The longest edge of the random minimal spanning tree, Annals of Applied Probability, 7, 1997, 340--361.
• 31: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 32: T. Phillips, S. Panwar and A. Tantawi. Connectivity properties of a packet radio network model. IEEE Trans on Information Theory, 35(5), 1044--1047, 1989.
• 33: P. Piret. On the connectivity of radio networks. IEEE Trans on Information Theory, 37(5), 1490--1492, 1991.
• 34: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January 2003 [doi>10.1109/TMC.2003.1195149]
• 35: A. Tsirigos, Z. Haas, S. Tabrizi. Multipath routing in mobile adhoc networks or how to route in the presence of topological changes. IEEE MILCOM, 2001.