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

On the Sensitivity of the Critical Transmission Range: Lessons from the Lonely Dimension

By Armand M. Makowski, Department of Electrical and Computer Engineering, and Institute for System Research, University of Maryland, USA, armand@isr.umd.edu | Guang Han, SAP, USA, guang.han@sap.com

 
Suggested Citation
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

Publication Date: 18 Sep 2013
© 2013 A. Makowski and G. Han
 
Subjects
Modeling and Analysis,  Scalability,  Stochastic Networks
 
Keywords
Connectivity, One-dimensional disk models, Geometric random graphs, Zero-one laws, Critical transmission range
 

Free Preview:

Download extract

Share

Journal details

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 

Abstract

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.

DOI:10.1561/1300000029

Book details

ISBN: 978-1-60198-706-8
118 pp. $85.00
Buy book (pb)
 
ISBN: 978-1-60198-707-5
118 pp. $115.00
Buy E-book (.pdf)
Table of contents:
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

On the Sensitivity of the Critical Transmission Range

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.

 
NET-029