Foundations and Trends® in Networking >
Vol 6 > Issue 4

Armand M. Makowski and Guang Han (2013), "On the Sensitivity of the Critical Transmission Range: Lessons from the Lonely Dimension", Foundations and TrendsĀ® in Networking: Vol. 6: No. 4, pp 287-399. http://dx.doi.org/10.1561/1300000029

© 2013 A. Makowski and G. Han

Connectivity, One-dimensional disk models, Geometric random graphs, Zero-one laws, Critical transmission range

Download article
**In this article:**

1. Introduction

2. The One-dimensional Model

3. The Uniform Case: Maximal Spacings

4. The Uniform Case: Counting Breakpoint Nodes

5. The Uniform Case: Proofs for Chapter 4

6. From Uniform to Non-uniform Node Placement

7. The Non-uniform Case with *f*_{*} > 0: A Strong Zero-one Law

8. The Non-uniform Case with *f*_{*} > 0: A Very Strong Zero-one Law

9. The Non-uniform Case with *f*_{*} > 0: A Proof of Theorem 8.1

10. The Non-uniform Case with *f*_{*} = 0: Vanishing Densities at Isolated Points

Acknowledgments

References

We consider geometric random graphs where *n* points are distributed independently on the unit interval [0, 1] according to some probability distribution function *F* with density function *f*. Two nodes communicate with each other if their distance is less than some transmission range. For this class of random graphs, we survey results concerning the existence of zero-one laws for graph connectivity, the type of the zero-one law obtained under specific assumptions on the density function *f*, the form of its critical scaling and its dependence on *f*, and the width of the corresponding phase transitions. This is motivated by the desire to understand how node distribution affects the critical transmission range as specified by the disk model. Engineering implications are discussed for power allocation.

1. Introduction

2. The One-dimensional Model

3. The Uniform Case: Maximal Spacings

4. The Uniform Case: Counting Breakpoint Nodes

5. The Uniform Case: Proofs for Chapter 4

6. From Uniform to Non-uniform Node Placement

7. The Non-uniform Case with *f*_{*} > 0: A Strong Zero-one Law

8. The Non-uniform Case with *f*_{*} > 0: A Very Strong Zero-one Law

9. The Non-uniform Case with *f*_{*} > 0: A Proof of Theorem 8.1

10. The Non-uniform Case with *f*_{*} = 0: Vanishing Densities at Isolated Points

Acknowledgments

References

In large-scale ad-hoc wireless networks, individual nodes communicate directly and reliably only with their neighbors, namely those nodes within their transmission range. A basic question is to determine the critical transmission range, that is, the smallest transmission range value that enables network connectivity amongst participating nodes. On the *sensitivity of the critical transmission range: Lessons from the lonely dimension* discusses this important resource allocation issue in the context of a simple one-dimensional disk model. It carefully explores how properties of the node distribution affect the critical transmission range, and develop engineering implications for power allocation. Interest in the one-dimensional stems from the fact that a complete set of results is available in that case, suggesting appropriate versions in the less developed higher dimensional situation, possibly by formal transfer.